package com.learn.tree;

/**
 * 找到两个节点最近的父节点
 */
public class FindParent {
    public static class Node {
        private Node left;
        private Node right;
        private int value;

        public Node(int value) {
            this.value = value;
        }
    }


    public static class Info {

        //交汇点

        private Node ans;
        private boolean findO1;
        private boolean findO2;

        public Info(Node ans, boolean findO1, boolean findO2) {
            this.ans = ans;
            this.findO1 = findO1;
            this.findO2 = findO2;
        }
    }


    public Node findParent(Node head, Node o1, Node o2) {
        return process(head, o1, o2).ans;
    }

    public Info process(Node x, Node o1, Node o2) {
        if (x == null) {
            return new Info(null, false, false);
        }

        Info leftInfo = process(x, o1, o2);
        Info rightInfo = process(x, o1, o2);

        boolean findO1 = x == o1 || leftInfo.findO1 || rightInfo.findO1;
        boolean findO2 = x == o2 || leftInfo.findO2 || rightInfo.findO2;
        Node ans = null;

        //如果在左树上找到父，则最近父节点为左树上的
        if (leftInfo.ans != null) {
            ans = leftInfo.ans;
        }
        //如果在右树上找到父，则最近父节点为右树上的
        if (rightInfo.ans != null) {
            ans = rightInfo.ans;
        }

        if (ans == null) {
            //如果左树和右树上均没找到最近父节点，且左树发现O1,右树发现O2,则最近父节点为x
            if (leftInfo.findO1 && rightInfo.findO2) {
                ans = x;
            }
        }

        return new Info(ans, findO1, findO2);
    }
}
